public class Test {
    // 题目1：二叉树的最小深度
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    }

    // 题目2：平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = height(root.left);
        if(left < 0) return -1;
        int right = height(root.right);
        if(right < 0) return -1;
        if(Math.abs(left - right) > 1) return -1;
        return (left < right ? right : left) + 1;
    }

    // 题目3：二叉树的坡度
    int ret;
    public int findTilt(TreeNode root) {
        tilt(root);
        return ret;
    }
    public int tilt(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = tilt(root.left);
        int right = tilt(root.right);
        ret += Math.abs(left - right);
        return left + right + root.val;
    }

    // 题目4：二叉树的直径
    int maxLen;
    public int diameterOfBinaryTree(TreeNode root) {
        diameter(root);
        return maxLen;
    }
    public int diameter(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = diameter(root.left); // 以root为根节点，左边有多少个结点意味着有多少条边，右边也一样
        int right = diameter(root.right);
        maxLen = Math.max(maxLen, left + right);
        return (left < right ? right : left) + 1;
    }

    // 题目5：二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null) return right;
        if(right == null) return left;
        return root;
    }

    // 题目6：二叉搜索树的最近公共祖先 ⭐
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if( q.val >= root.val && p.val <= root.val || q.val <= root.val && p.val >= root.val){
            return root;
        }
        if(q.val < root.val && p.val < root.val){
            return lowestCommonAncestor1(root.left, p, q);
        }
        if(q.val > root.val && p.val > root.val){
            return lowestCommonAncestor1(root.right, p, q);
        }
        return null;
    }

}
